﻿
namespace ZDS

open System
open System.Collections
open System.Collections.Generic

type ZStaticListNode<'t> =
    {
        mutable Value : 't
        mutable Next : int
    }

type ZStaticLinkList<'t>(m_capacity) =
    do
        if m_capacity < 0 then
            invalidArg "capacity" "capacity < 0"

    let m_array = Array.zeroCreate<ZStaticListNode<'t>> (1+m_capacity)
    let mutable m_rear = 0 // points to the PreHead node
    let mutable m_free = 1
    let mutable m_size = 0

    do
        // first node is a special node, prehead
        m_array.[0] <- {Value = Unchecked.defaultof<'t>;Next = -1}
        for index = 1 to m_capacity do
            m_array.[index] <- {Value = Unchecked.defaultof<'t>;Next = index+1}

        // the last node of the free node must have Next to be -1
        // to indicate the end of the availabe chain
        m_array.[m_capacity].Next <- -1

    let nth_node n =
        if n = -1 then
            m_array.[0],0
        elif n = (m_size - 1) then
            m_array.[m_rear],m_rear
        else
            let mutable pos = 0
            for i = 1 to (n+1) do
                pos <- m_array.[pos].Next
            m_array.[pos],pos

    member this.Capacity = m_capacity
    member this.Size = m_size

    member this.Append value = 
        if m_free > 0 then
            m_array.[m_free].Value <- value

            m_array.[m_rear].Next <- m_free
            m_rear <- m_free

            m_free <- m_array.[m_free].Next
            m_array.[m_rear].Next <- -1

            m_size <- m_size + 1

        else
            raise <| ZError(ErrorCode.Full)

    member this.Item
        with get index =
            if index >=0 && index < m_size then
                let node,_ = nth_node index
                node.Value
            else
                raise <| ZError(ErrorCode.OutofRange)
        and set index newvalue =
            if index >= 0 && index < m_size then
                let node,_ = nth_node index
                node.Value <- newvalue
            else
                raise <| ZError(ErrorCode.OutofRange)

    member this.Insert index value =
        if m_size >= m_capacity then
            raise <| ZError(ErrorCode.Full)

        assert (m_free > 0)
        if index >= 0 && index <= m_size then
            let newFree = m_array.[m_free].Next

            let prev,_ = nth_node (index-1)
            m_array.[m_free].Value <- value
            m_array.[m_free].Next <- prev.Next
            prev.Next <- m_free

            if index = m_size then
                m_rear <- m_free

                // because its previous one is the old rear
                // copy the next from the old rear, so it next will definitely be -1
                assert (m_array.[m_rear].Next = -1)

            m_free <- newFree
            m_size <- m_size + 1
            
        else
            raise <| ZError(ErrorCode.OutofRange)

    member this.Remove index =
        if m_size = 0 then
            raise <| ZError(ErrorCode.Empty)

        if index >= 0 && index < m_size then
            let prevNode,prevPos = nth_node (index-1)

            let toremove = prevNode.Next
            prevNode.Next <- m_array.[toremove].Next

            m_array.[toremove].Next <- m_free
            m_free <- toremove

            if index = (m_size-1) then
                m_rear <- prevPos
                assert (m_array.[m_rear].Next = -1)

            m_size <- m_size-1
            m_array.[m_free].Value
        else
            raise <| ZError(ErrorCode.OutofRange)

    // ################## interface IEnumerable
    interface IEnumerable<'t> with
        member this.GetEnumerator() =
            new ZStaticListIterator<'t>(m_array) :> IEnumerator<'t>

    interface IEnumerable with
        member this.GetEnumerator() =
            new ZStaticListIterator<'t>(m_array) :> IEnumerator

and ZStaticListIterator<'t>(m_array : ZStaticListNode<'t>[])=
    let mutable m_index = 0

    interface IDisposable with
        member this.Dispose() =
            ()

    interface IEnumerator<'t> with
        member this.Current =
            m_array.[m_index].Value

    interface IEnumerator with
        member this.MoveNext() =
            m_index <- m_array.[m_index].Next
            m_index > 0

        member this.Reset() =
            m_index <- 0

        member this.Current =
            box (this :> IEnumerator<'t>).Current
            
            

